package main.leetcode.clockin.Auguest;

/**
 * 647. 回文子串
 *
 * <p>给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
 *
 * <p>具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 *
 * <p>示例 1：输入："abc" 输出：3 解释：三个回文子串: "a", "b", "c"
 *
 * <p>示例 2：输入："aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
 *
 * <p>提示：输入的字符串长度不会超过 1000 。
 */
public class day19 {
    public static void main(String[] args) {
        System.out.println(new day19().countSubstrings("abcba"));
    }

    public int countSubstrings(String s) {
        int res = 0;
        int n = s.length();
        // 以 [0 - i] 为目标串，以 l 往左，以 r 往右
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2;
            // 奇数，r 从中心右边一位为起点；偶数，r 从中心右边一位为起点。区别在于 l 已经在中心，或者中心左边一位
            int r = l + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
                ++res;
            }
        }
        return res;
    }
}
